package bfs

import (
	"arithmetic/structure"
)

//广度优先搜索算法
func BFS(g *structure.Graph, startNode *structure.Node, targetNode *structure.Node) bool {
	var searchList = make([]*structure.Node, 0)
	searchList = append(searchList, startNode)
	//创建map储存搜索过的节点
	var searchedMap = make(map[*structure.Node]byte)
	//初始化，全部节点设置为0表示未搜索
	for i := range g.Nodes {
		searchedMap[g.Nodes[i]] = 0
	}
	for ; len(searchList) > 0; searchList = searchList[1:] {
		if searchList[0].Value == targetNode.Value {
			return true
		} else {
			currentNode := structure.Node{Value: searchList[0].Value}
			for i := range g.Edges[currentNode] {
				//如果当前的子节点未被搜索过，则添加改子节点到待搜索队列
				if searchedMap[g.Edges[currentNode][i]] == 0 {
					searchList = append(searchList, g.Edges[currentNode][i])
				}
			}
			searchedMap[searchList[0]] = 1 //将当前节点设置为已搜索
		}
	}
	return false
}
